package fun.coding.leetcode;

/**
 * http://oj.leetcode.com/problems/gas-station/
 */
public class GasStation {
    
    public static void main(String[] args) {
        int[] gas = {67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66};
        int[] cost = {27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
        
        GasStation gs = new GasStation();
        System.out.println("result is " + gs.canCompleteCircuit(gas, cost));
        
    }

    // This method is purely O(N). 
    // http://fisherlei.blogspot.com/2013/11/leetcode-gas-station-solution.html
    // The main point is if sum(diff) < 0, there is no way you could do it. 
    // Then the problem becomes find the starting index for a sequence that sum(diff) is always > 0. 
    // If that is not the case, then means starting point is not there. 
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] diff = new int[gas.length];
        
        int sum = 0;
        for (int i = 0; i < gas.length; ++i) {
            diff[i] = gas[i] - cost[i];
            sum += diff[i];
        }
        
        if (sum < 0) {
            return -1;
        }
        
        int s = 0;
        int start = 0;
        for (int i = 0; i < diff.length; ++i) {
            s += diff[i];
            if (s < 0) {
                s = 0;
                start = i + 1;
            }
        }
        
        return start;
    }
    
    // This has heuristics, but worst case is still O(N^2).
    public int canCompleteCircuitHeuristics(int[] gas, int[] cost) {
        int[] diff = new int[gas.length];
        
        int sum = 0;
        for (int i = 0; i < gas.length; ++i) {
            diff[i] = gas[i] - cost[i];
            sum += diff[i];
        }
        
        for (int i = 0; i < diff.length; ++i) {
            System.out.print(diff[i] + " ");
        }
        
        if (sum < 0) {
            return -1;
        } else {
            return findIndex(diff);
        }
        
    }
    
    private int findIndex(int[] diff) {
        for (int i = 0; i < diff.length; ++i) {
            if (diff[i] < 0) continue;
            
            int count = 0;
            int accum = 0;
            int j = i;
            while (count < diff.length) {
                accum += diff[j % diff.length];
                System.out.println("index is " + j + " and accum is " + accum);
                if ((accum + diff[(j + 1) % diff.length]) < 0) break;
                j++;
                count++;
            }
            
            if (count == diff.length) {
                return i;
            }
        }
            
        return -1;
    }
    
    // This naive way will be O(N^2) and will time exceeded. 
    public int canCompleteCircuitNaive(int[] gas, int[] cost) {
        if (gas == null || cost == null) return -1;
        
        for (int i = 0; i < gas.length; ++i) {
            int accumGas = 0;
            int count = 0;
            int j = i;
            boolean canComplete = true;
            while (count < cost.length) {
                accumGas += gas[j];
                if (accumGas < cost[j]) {
                    canComplete = false;
                    break;
                } else {
                    accumGas -= cost[j];
                    j = (j + 1) % cost.length;
                }
                count++;
            }
            
            if (canComplete) {
                return i;
            }
        }
        
        return -1;
    }
    
}
